class Solution {
public:
    vector<string> ret;
    string path;
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }
    void dfs(string s, int pos) {
        if (path.size() == s.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = pos; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                path.push_back(s[i]);
                dfs(s, i + 1);
            } else {
                path.push_back(s[i]);
                dfs(s, i + 1);
                path.pop_back();
                s[i] = s[i] ^ 32;
                path.push_back(s[i]);
                dfs(s, i + 1);
            }
            path.pop_back();
            return;
        }
    }
};